package lanqiao._02算法训练.page01;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。
 * 他拿出n个木棍，然后选出其中一些粘成一根长的，然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。
 * 输入格式
 * 　　第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。
 * 输出格式
 * 　　一个数，最大的长度。
 * 样例输入
 * 4
 * 1 2 3 1
 * 样例输出
 * 3
 * 数据规模和约定
 * 　　n<=15
 * 思路：
 * 将所有数分成两部分
 * 深度搜索 枚举
 * 对于当前数有三种决策：
 * 1.放左堆
 * 2.放右堆
 * 3.舍弃
 * @since 2022 - 10 - 29 - 13:28
 */
public class _04无聊的逗 {
}
class Main4{
    static int max = -1;
    static int[] nums;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        nums = new int[n];
        int sum = 0;
        for(int i = 0; i < n; i++){
            nums[i] = sc.nextInt();
            sum += nums[i];
        }
        dfs(0, sum, 0);
        System.out.println(max);
    }

    /**
     * 查找nums 数组分成两部分相等的堆，得到最大和
     * @param index 从0开始
     * @param left 左堆，初始为 sum(nums)
     * @param right 右堆，初始为 0
     */
    public static void dfs(int index, int left, int right){
        if(left == right){
            //记录最大的情况
            max = Math.max(max, left);
            return;
        }
        //剪枝: 不可能相等了
        if(left < right) return;
        if(index < nums.length){
            //选择当前数到右堆
            dfs(index + 1, left - nums[index], right + nums[index]);
            //不选择当前数，还放在左堆
            dfs(index + 1, left, right);
            //舍弃当前数
            dfs(index + 1, left - nums[index], right);
        }

    }
}